/**
 * 108. 将有序数组转换为二叉搜索树
 * https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
 */
public class Solutions_108 {
    public static void main(String[] args) {
        int[] nums = {-10, -3, 0, 5, 9};  // output: {0, -3, 9, -10, null, 5}
        TreeNode result = sortedArrayToBST(nums);
        System.out.println(result);
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    public static TreeNode dfs(int[] nums, int left, int right) {
        if (left >= right) {
            // 结束条件
            return left == right ? new TreeNode(nums[left]) : null;
        }
        // 二分法，找到中间元素，即是根节点，保证左右元素个数相差最多一个
        int mid = left + (right - left) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        // 以 mid 为界，nums 的左边元素构成 root 的左子树，右边元素构成 root 的右子树
        root.left = dfs(nums, left, mid - 1);
        root.right = dfs(nums, mid + 1, right);
        return root;
    }
}
